import java.util.*;
public class Test {
    // 题目1：二叉树的右视图
    List<Integer> list = new LinkedList<>();
    int isFirstTime;
    public List<Integer> rightSideView(TreeNode root) {
        dsf(root, 1);
        return list;
    }
    public void dsf(TreeNode root, int depth){
        if(root == null){
            return;
        }
        if(depth > isFirstTime){
            list.add(root.val);
            isFirstTime++;
        }
        dsf(root.right, depth + 1);
        dsf(root.left, depth + 1);
    }

    // 题目2：两棵二叉搜索树中的所有元素按升序排序
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list = new LinkedList<>();
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();
        while(root1 != null || root2 != null || !stack1.isEmpty() || !stack2.isEmpty()){
            while(root1 != null){
                stack1.push(root1);
                root1 = root1.left;
            }
            while(root2 != null){
                stack2.push(root2);
                root2 = root2.left;
            }
            // stack1 和 stack2 不能同时为空
            // 如果同时为空，意味着一开始时的 root1和root2都是null，再加上两个栈都为空，怎么进入最外层的循环呢？
            // 出来之后，root1和root2都是null！
            // 使用 peek ， 符合条件的才弹出，不符合条件的不需要再放回去。
            if(stack1.isEmpty()){
                list.add(stack2.peek().val);
                root2 = stack2.pop().right;
                continue;
            }
            if(stack2.isEmpty()){
                list.add(stack1.peek().val);
                root1 = stack1.pop().right;
                continue;
            }
            if(stack1.peek().val <= stack2.peek().val){
                list.add(stack1.peek().val);
                root1 = stack1.pop().right;
            }else{
                list.add(stack2.peek().val);
                root2 = stack2.pop().right;
            }
        }
        return list;
    }
    // 题目3：递增顺序搜索树
    // 将一颗二叉搜索树按中序遍历的方式将其重新排列为一棵递增顺序搜索树，
    // 使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
    // 二叉搜索树 ，中序遍历：左中右的递增的，右中左是逆序的吗？
    static TreeNode node = new TreeNode(-1);
    static TreeNode node0 = node;
    public static TreeNode increasingBST(TreeNode root) {
        dsf(root);
        return node.right;
    }
    public static void dsf(TreeNode root){
        if(root == null){
            return;
        }
        dsf(root.left);
        node0.right = new TreeNode(root.val);
        node0 = node0.right;
        dsf(root.right);
    }

    public static void main1(String[] args) {
        TreeNode node = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(7);
        node.left = node1;
        node.right = node2;
        TreeNode ret = increasingBST(node);
        System.out.println(ret);
    }
}
